package com.lwx.leetcode.backtrack;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class Offer47 {
    public static void main(String[] args) {
        int[][] grid = {{1,3,1},{1,5,1},{4,2,1}};
        Offer47 o = new Offer47();
        int ret = o.maxValue(grid);
        System.out.println(ret);
    }
    int[][] direction = {{1,0},{0,1}};
    List<Integer> allValue;
    boolean[][] visited;
    int m;
    int n;
    public int maxValue(int[][] grid) {
        if(grid == null || grid.length == 0 || grid[0].length == 0){
            return 0;
        }
        int maxValue = Integer.MIN_VALUE;
        m = grid.length;
        n = grid[0].length;
        allValue = new ArrayList<>();
        visited = new boolean[grid.length][grid[0].length];
        dfs(grid,0,0,new LinkedList());
        for (int i = 0; i < allValue.size(); i++) {
            if(allValue.get(i) > maxValue){
                maxValue = allValue.get(i);
            }
        }
        return maxValue;
    }

    public void dfs(int[][] grid, int x, int y, Deque q){
        //到达右下角
        if(x == m-1 && y == n-1){
            if(inArea(x,y) &&!visited[x][y]){
                visited[x][y] = true;
                q.addLast(grid[x][y]);
                int sum = 0;
                ArrayList<Integer> list = new ArrayList<>(q);
                for (int i = 0; i < list.size(); i++) {
                    sum += list.get(i);
                }
                allValue.add(sum);
                q.removeLast();
                visited[x][y] = false;
            }
            return;
        }
        if(inArea(x,y) &&!visited[x][y]){
            visited[x][y] = true;
            q.addLast(grid[x][y]);
            for (int i = 0; i < 2; i++) {
                //下、右
                int newX = x + direction[i][0];
                int newY = y + direction[i][1];
                dfs(grid,newX,newY,q);
            }
            q.removeLast();
            visited[x][y] = false;
        }
    }

    public boolean inArea(int x,int y){
        if(x >= 0 && x < m && y >= 0 && y < n){
            return true;
        }
        return false;
    }
}
